The present invention relates generally to wireless telephone cryptography. More particularly, the invention relates to an improved security cryptosystem for rapid and secure encryption in a wireless telephone system without requiring large amounts of additional system resources.
Wireless telephony uses messaging for several purposes including, for example, conveying status information, reconfiguring operating modes, handling call termination, and conveying system and user data such as a subscriber""s electronic serial number and telephone number, as well as conversations and other data transmitted by the user. Unlike ordinary wire telephony, in which a central serving station is connected to each subscriber by wire, thus ensuring a fair degree of protection from eavesdropping and tampering by an unauthorized party (attacker), wireless telephone serving stations (i.e., base stations) must transmit and receive messages via signals over the air, regardless of the physical location of the subscribers.
Because the base station must be able to send and receive messages to and from a subscriber anywhere, the messaging process is wholly dependent on signals received from and sent to the subscriber equipment. Because the signals are transmitted over the air, they can be intercepted by an eavesdropper or interloper with the right equipment.
If a signal is transmitted by a wireless telephone in plaintext, a danger exists that an eavesdropper will intercept the signal and use it to impersonate a subscriber, or to intercept private data transmitted by the user. Such private data may include the content of conversations. Private data may also include non-voice data transmitted by the user such as, for example, computer data transmitted over a modem connected to the wireless telephone, and may also include bank account or other private user information transmitted typically by means of keypresses. An eavesdropper listening to a conversation or intercepting non-voice data may obtain private information from the user. The message content of an unencrypted telephone signal (i.e., plaintext signal) is relatively easily intercepted by a suitably adapted receiver.
Alternatively, an interloper can interect himself into an established connection by using a greater transmitting power, sending signals to the base station, and impersonating a party to the conversation.
In the absence of applying cryptography to messages being transmitted by wireless signals, unauthorized use of telephone resources, eavesdropping of messages, and impersonation of called or calling parties during a conversation are possible. Such unauthorized interloping and/or eavesdropping has in fact proven to be a grave problem and is highly undesirable.
The application of cryptography to wireless telephone applications offers a solution to the security problems discussed above, but the application of standard cryptography methods to wireless telephony has encountered significant difficulties due to the computationally-intensive nature of these methods. Specifically, these methods are subject to the constraints imposed by the desire to furnish a small wireless handset and the constraints on processing power imposed by the small size of the handset. The processing power present in typical wireless handsets is insufficient to handle the processing requirements of commonly known cryptographic algorithms such as DES (Data Encryption Standard). Implementing such a commonly known cryptographic algorithm in a typical wireless telephone system would potentially increase the time needed to process signals (i.e., encrypt and decrypt), thereby causing unacceptable delays for subscribers.
One cryptographic system for wireless telephony is disclosed in Reeds U.S. Pat. No. 5,159,634 (xe2x80x9cReedsxe2x80x9d), incorporated herein by reference. Reeds describes a cryptographic process known as the CMEA (xe2x80x9cCellular Message Encryption Algorithmxe2x80x9d) process. Central to the operation of the CMEA is the tbox function, which is a one to one mapping of one octet to another, using a known table and a secret key. Beginning with an initial index, key material is combined with table material in multiple iterations to perform the mapping. The tbox function can be implemented either as a function call or as a static memory-resident tbox table. The tbox table""s purpose, when implemented as in the latter case, is to allow significant speed-up of encryption for a given security level.
Enhancements to the CMEA process exist, disclosed in our patent application Ser. No. 09/059,107, entitled xe2x80x9cMethods and Apparatus for Multiple-Iteration CMEA Encryption and Decryption for Improved Security for Cellular Telephone Messagesxe2x80x9d filed on Apr. 13, 1998, and our patent application Ser. No. 09/059,116, entitled xe2x80x9cMethods and Apparatus for Enhanced Security Expansion of a Secret Key Into a Lookup Table for Improved Security for Wireless Telephone Messagesxe2x80x9d filed on Apr. 13, 1998. These enhancements provide significantly increased security to the CMEA process. However, additional enhancements would provide further increased security.
The CMEA process of the prior art may be significantly improved as described in greater detail below. These improvements provide an additional degree of security which is highly advantageous. The cryptographic process of Reeds can be improved through modification and simplification. Either the original process of Reeds, or the modified and simplified process, which will hereinafter be referred to as the modified CMEA, can be used in an improved process including further improvements which are collectively termed ECMEA (Enhanced CMEA).
The present invention provides an additional degree of security to cryptographic algorithms such as CMEA by providing a forward enhanced CMEA, or ECMEA, process, as well as a reverse ECMEA process. Information encrypted by the forward process is decrypted by the reverse process, and information encrypted by the reverse process is decrypted by the forward process. The forward ECMEA process subjects the message to a transformation before an iteration of the CMEA process, and an inverse transformation after the iteration of the CMEA process. The iteration of the CMEA process may be either the original process of Reeds, or the modified CMEA process. Where the original process of Reeds is meant, the term xe2x80x98original CMEAxe2x80x99 will be used, and where the modified CMEA process is meant, the term xe2x80x98modified CMEAxe2x80x99 will be used. Where the term xe2x80x98CMEA processxe2x80x99 is used without further definition, either the original CMEA or the modified CMEA may be used, the choice being dependent on design preference. It is preferred, however, that the modified CMEA be used unless design preferences suggest otherwise. The iteration of the CMEA process is enhanced by permutation of the inputs to the tbox function by a first secret offset. The tbox function employed by the CMEA process is enhanced through the use of an involutary lookup table. The transformation and inverse transformation employ the first secret offset and a second secret offset. The transformation performs an offset rotation of the first offset and an involutary lookup of each octet, and performs bit-trades between each pair of adjacent octets. For all octets except the last octet, the transformation performs a random octet permutation, which is an exchange between the previous octet and a random one below it. The transformation also performs a final octet permutation, which is an exchange between the last octet and a random one below it.
The inverse transformation performs an initial offset rotation on the second offset, and an initial octet permutation on the last octet, which is an exchange of the last octet with a random one below it. For all octets except the last octet, the inverse transformation performs a random octet permutation, which is an exchange between the octet and a random one below it. The transform performs bit-trades between each pair of adjacent octets, and performs an involutary lookup of each octet followed by an offset rotation of the second offset.
Since the inverse transformation uses the first and second offsets in the opposite order compared to the transformation, the forward ECMEA process as a whole is not self-inverting. In order to decrypt text encrypted by the forward ECMEA process, or to encrypt text for decryption by the forward ECMEA process, a reverse ECMEA process is used. The reverse ECMEA process employs a reverse transformation, followed by an iteration of the CMEA process, followed by a reverse inverse transformation. The reverse transformation is identical to the transformation except that the use of the first and second offsets is reversed. That is, where the transformation uses the first offset, the reverse transformation uses the second offset, and where the transformation uses the second offset, the reverse transformation uses the first offset. Similarly, the reverse inverse transformation is identical to the inverse transformation except that the use of the first and second offsets is reversed. That is, where the inverse transformation uses the first offset, the reverse inverse transformation uses the second offset, and where the inverse transformation uses the second offset, the reverse inverse transformation uses the first offset.
The iteration of the CMEA algorithm may be enhanced by permutation of the inputs to the tbox function by the first secret offset. The tbox function employed by the CMEA algorithm is enhanced through the use of an involutary lookup table.
The forward ECMEA process decrypts text encrypted by the reverse ECMEA process, and the reverse ECMEA process decrypts text encrypted by the forward ECMEA process. The enhancements discussed above improve CMEA, and can be implemented to operate quickly and efficiently in a small computer such as is commonly used in a mobile wireless transceiver.
A cryptographic system according to the present invention may suitably employ the enhanced tbox function, also using first and second offsets to permute inputs to the enhanced tbox function and for use in performing the transformation and reverse transformation and inverse transformation and reverse inverse transformation. Each offset is created using two secret values and an external cryptosync value. The secret values may be generated by any of a number of techniques commonly known in the art. In some applications outside of the wireless area, the external cryptosync value used to encrypt a first message of a call is an initialization vector. Then for subsequent messages, the external cryptosync value is the first two octets of ciphertext from a previously encrypted message.
In another aspect of the present invention, a telephone system according to the present invention includes a mobile station and a base station. Each of the mobile station and the base station generates text and supplies it to an I/O interface which identifies it as generated text and supplies the text and the identification to an encryption/decryption processor, which in turn encrypts the text and supplies it to a transceiver for transmission. When the apparatus receives a transmission via the transceiver, the transmission is identified as incoming ciphertext, and the ciphertext and the identification are supplied to the encryption/decryption processor which decrypts the ciphertext and supplies it as text to the I/O processor for routing to its destination. The mobile station preferably employs the forward ECMEA process and the base station preferably employs the reverse ECMEA process.
A more complete understanding of the present invention, as well as further features and advantages of the invention, will be apparent from the following Detailed Description and the accompanying drawings.